package sort

// 快速排序
func quickSort(arr []int) {
    qsort(arr, 0, len(arr)-1)
}

func qsort(arr []int, left, right int) {
    if left > right {
        return
    }
    partition := partition(arr, left, right)
    qsort(arr, left, partition-1)
    qsort(arr, partition+1, right)
}

func partition(arr []int, left, right int) int {
    key := arr[left]
    lPos := left
    rPos := right + 1
    for {
        for {
            rPos--
            if rPos <= lPos || arr[rPos] < key {
                break
            }
        }

        for {
            lPos++
            if lPos >= rPos || arr[lPos] > key {
                break
            }
        }

        if lPos >= rPos {
            break
        } else {
            arr[lPos], arr[rPos] = arr[rPos], arr[lPos]
        }
    }

    arr[left], arr[rPos] = arr[rPos], arr[left]

    return rPos
}
